//给你一个链表数组，每个链表都已经按升序排列。 
//
// 请你将所有链表合并到一个升序链表中，返回合并后的链表。 
//
// 
//
// 示例 1： 
//
// 输入：lists = [[1,4,5],[1,3,4],[2,6]]
//输出：[1,1,2,3,4,4,5,6]
//解释：链表数组如下：
//[
//  1->4->5,
//  1->3->4,
//  2->6
//]
//将它们合并到一个有序链表中得到。
//1->1->2->3->4->4->5->6
// 
//
// 示例 2： 
//
// 输入：lists = []
//输出：[]
// 
//
// 示例 3： 
//
// 输入：lists = [[]]
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// k == lists.length 
// 0 <= k <= 10^4 
// 0 <= lists[i].length <= 500 
// -10^4 <= lists[i][j] <= 10^4 
// lists[i] 按 升序 排列 
// lists[i].length 的总和不超过 10^4 
// 
// Related Topics 堆 链表 分治算法 
// 👍 860 👎 0

package leetcode.editor.cn;

//Java：合并K个升序链表
public class P23MergeKSortedLists {

    //leetcode submit region begin(Prohibit modification and deletion)

    /*
     * 思路: 分治算法，参考算法的归并排序     将两个链表合并成一个，递归处理，利用k判断是否处理到了最后一层
     *
     * 这道题的测试用例非常恶心  lists = []，lists = [[]]  要返回null，不能返回 new ListNode()
     *
     * 执行用时： 3 ms , 在所有 Java 提交中击败了 81.94% 的用户 内存消耗： 42.4 MB , 在所有 Java 提交中击败了 8.47% 的用户
     *
     * */

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            if (lists.length == 0) {
                return null;
            }
            merge(0, 1, lists.length - 1, lists);
            return lists[0];
        }

        // 0 1 2    n = 3
        // 0 1 2 3   n = 4
        // 0 1 2 3 4 5 6   k=6
        // 0 1 2 3 4 5 6 7 k=7
        // 0 1   k=4

        /**
         * 描述：将数组每两个合并成一个，例如 数组的 0 1 2 3 4 5 6， 0 1 -> 0, 2 3 -> 1, 4 5 -> 2, 6->3
         *
         * @param head  开始的下标
         * @param tail  结束的下标
         * @param k     当前数组将要循环的最后一个元素的下标
         * @param lists 链表数组
         * @date: 2020/8/19 16:49
         */
        private void merge(int head, int tail, int k, ListNode[] lists) {
            if (k == 0) {
                return;
            }
            if (head > k) {
                k = head / 2 - 1;
                head = 0;
                tail = 1;
            }
            if (head == k) {
                lists[head / 2] = lists[head];
            } else {
                lists[head / 2] = mergeTwoLists(lists[head], lists[tail]);
            }
            merge(head + 2, tail + 2, k, lists);
        }

        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            ListNode node = new ListNode();
            ListNode last = node;

            while (l1 != null || l2 != null) {
                if (l1 == null) {
                    ListNode temp = new ListNode(l2.val);
                    last.next = temp;
                    last = temp;
                    l2 = l2.next;
                } else if (l2 == null) {
                    ListNode temp = new ListNode(l1.val);
                    last.next = temp;
                    last = temp;
                    l1 = l1.next;
                } else {
                    if (l1.val <= l2.val) {
                        ListNode temp = new ListNode(l1.val);
                        last.next = temp;
                        last = temp;
                        l1 = l1.next;
                    } else {
                        ListNode temp = new ListNode(l2.val);
                        last.next = temp;
                        last = temp;
                        l2 = l2.next;
                    }
                }
            }
            return node.next;
        }

    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new P23MergeKSortedLists().new Solution();

        ListNode node1 = new ListNode(5);
        node1 = add(node1, 4);
        node1 = add(node1, 1);

        ListNode node2 = new ListNode(4);
        node2 = add(node2, 3);
        node2 = add(node2, 1);

        ListNode node3 = new ListNode(6);
        node3 = add(node3, 2);

        ListNode[] node = new ListNode[3];
        node[0] = node1;
        node[1] = node2;
        node[2] = node3;
        ListNode tt = solution.mergeKLists(node);
        System.out.println(tt);
        // TO TEST
    }

    private static ListNode add(ListNode listNode, int x) {
        ListNode node = new ListNode(x);
        node.next = listNode;
        return node;
    }

}